package 剑指Offer._5160;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/18 13:36
 * 数组中数字出现的次数 II
 * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
 * 算法：位运算
 * 数字出现了三次，表示各位上 1 的个数是 3 的倍数
 * 计算每位上 1 的个数，然后取余 3，得到的就是结果
 */
public class _56II {
    public static void main(String[] args) {
        System.out.println(new _56II().singleNumber(new int[]{3, 4, 3, 3}));
    }

    public int singleNumber(int[] nums) {
        int[] cnt = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                if ((num & 1) == 1) ++cnt[i];
                num >>>= 1;
            }
        }
        System.out.println(Arrays.toString(cnt));
        for (int i = 0; i < 32; i++) cnt[i] %= 3;
        System.out.println(Arrays.toString(cnt));
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            ans <<= 1;
            ans |= cnt[i];
        }
        return ans;
    }

}
